package cn.cxq.learning.math;

import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.PriorityQueue;

/**
 * 牛客题霸-研发最爱考
 * 随时找到数据流的中位数
 * 时间限制：C/C++ 10秒，其他语言20秒 空间限制：C/C++ 256M，其他语言512M 热度指数：3933
 * 本题知识点： 堆
 *  算法知识视频讲解
 * 题目描述
 * 有一个源源不断的吐出整数的数据流，假设你有足够的空间来保存吐出的数。请设计一个名叫MedianHolder的结构，MedianHolder可以随时取得之前吐出所有数的中位数。
 * [要求]
 * 1. 如果MedianHolder已经保存了吐出的N个数，那么将一个新数加入到MedianHolder的过程，其时间复杂度是O(logN)。
 * 2. 取得已经吐出的N个数整体的中位数的过程，时间复杂度为O(1)
 *
 * 每行有一个整数opt表示操作类型
 * 若opt=1，则接下来有一个整数N表示将N加入到结构中。
 * 若opt=2，则表示询问当前所有数的中位数
 *
 * 示例1
 * 输入
 * 复制
 * [[1,5],[2],[1,3],[2],[1,6],[2],[1,7],[2]]
 * 返回值
 * 复制
 * [5,4,5,5.5]
 * 说明
 * 第一次查询时结构内的数为：5
 * 第二次查询时结构内的数为：3 5
 * 第二次查询时结构内的数为：3 5 6
 * 第二次查询时结构内的数为：3 5 6 7
 *
 * 示例2
 * 输入
 * 复制
 * [[2],[1,1],[2]]
 * 返回值
 * 复制
 * [-1,1]
 *  关联企业
 * Ucloud腾讯微软字节跳动
 *  关联职位
 * 研发算法
 */
public class FlowMedian {

    PriorityQueue<Integer> smallHeap = new PriorityQueue<>();
    PriorityQueue<Integer> bigHeap = new PriorityQueue<>((o1, o2) -> o2 - o1);
    int count = 0;

    @Test
    public void test () {
        double[] result = flowmedian(new int[][]{{1, 5}, {2}, {1, 3}, {2}, {1, 6}, {2}, {1, 7}, {2}});
        System.out.println();
    }

    public double[] flowmedian (int[][] operations) {
        // write code here
        ArrayList<Double> list = new ArrayList<>();

        for (int i = 0; i < operations.length; i++) {
            if (operations[i][0] == 1) {
                if (count % 2 == 0) {
                    smallHeap.offer(operations[i][1]);
                    bigHeap.offer(smallHeap.poll());
                } else {
                    bigHeap.offer(operations[i][1]);
                    smallHeap.offer(bigHeap.poll());
                }
                count++;
            } else {
                if (count % 2 == 1) {
                    list.add((double) bigHeap.peek());
                } else {
                    if (count == 0) {
                        list.add((double) -1);
                    } else {
                        list.add((smallHeap.peek() + bigHeap.peek()) / 2.0);
                    }
                }
            }
        }



        return list.stream().mapToDouble(Double::doubleValue).toArray();
    }
}
